package exercises.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/repeated-dna-sequences/">
 * 187. 重复的DNA序列</a>
 *
 * <p><span color="#87CEEB">描述:</span>所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
 * <p>
 * 编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
 * 输出：["AAAAACCCCC","CCCCCAAAAA"]
 * <p>
 * 示例 2：
 * <p>
 * 输入：s = "AAAAAAAAAAAAA"
 * 输出：["AAAAAAAAAA"]
 *
 * @author or2
 * @date 2021年10月08日 时间: 7:46
 */
public class No187 {
    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() < 10)
            return Collections.emptyList();

        int hash = 0;
        for (int i = 0; i < 10; i++) {
            hash <<= 2;
            switch (s.charAt(i)) {
                case 'C' -> hash |= 0b01;
                case 'G' -> hash |= 0b10;
                case 'T' -> hash |= 0b11;
            }
        }
        var map = new HashMap<Integer, Integer>();
        /* 存放字符串的最后的下标 */
        map.put(hash, 10);

        var ans = new ArrayList<String>();

        for (int i = 10, length = s.length(); i < length; i++) {
            hash = (hash << 2) & (0xFFFFF);
            switch (s.charAt(i)) {
                case 'C' -> hash |= 0b01;
                case 'G' -> hash |= 0b10;
                case 'T' -> hash |= 0b11;
            }
            if (map.containsKey(hash)) {
                Integer endIndex = map.get(hash);
                /* 去重 */
                if (endIndex != -1) {
                    ans.add(s.substring(endIndex - 10, endIndex));
                    map.put(hash, -1);
                }
            } else
                map.put(hash, i + 1);
        }

        return ans;
    }
}
